/**
@author: LHG
@date: 2021/7/15
@note:
**/
package main

//import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的.

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
合并两个有序链表
*/
func main() {
	mergeTwoLists(new(ListNode), new(ListNode))
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	/*
		l1 l2 都是有序的，
		注意：两个链表的头结点都是存了数据的
		拼接一根新链表作为返回值
	*/

	if l1 == nil && l2 == nil {
		return nil
	}

	//新链表的头结点
	head := new(ListNode)

	temp1 := l1
	temp2 := l2
	for true {
		if temp1 == nil {
			return temp2
		} else if temp2 == nil {
			return temp1
		} else {
			if temp1.Val < temp2.Val {
				if head.Next == nil {
					head.Val = temp1.Val
					head.Next = temp1
				} else {
					node := new(ListNode)
					node.Val = temp1.Val
					head.Next = node
				}
				temp1 = temp1.Next
			} else {
				if head.Next == nil {
					head.Val = temp2.Val

				} else {
					node := new(ListNode)
					node.Val = temp2.Val
					head.Next = node
				}
				temp2 = temp2.Next
			}
		}
		if temp1.Next == nil && temp2.Next == nil {
			break
		}
	}
	return head
}
